The present disclosure generally relates to methods, systems and media for making Transmission Control Protocol (TCP) robust to packet re-ordering. More specifically, the present disclosure uses one or more computer systems that adapt the fast retransmit threshold (FRT) to make TCP robust to non-congestion events by adjusting the current or initial FRT value, which may be a hard-coded 3, upon FRT's value being relative to the size of the congestion window.
Transmission Control Protocol (TCP) generally provides reliable, in-order delivery of a stream of bytes, i.e., data, which makes it suitable for applications like file transfer and e-mail. TCP, then, is the transport protocol that manages the individual “conversations” between web servers and web clients. As previously stated otherwise, TCP divides the HTTP messages into smaller pieces, called segments, to be sent to the destination client. It is also responsible for controlling the size and rate at which messages are exchanged between the server and the client.
For ordering of segments/packets, TCP uses a “sequence number” to identify each byte of data. The sequence number identifies the order of the bytes sent from each computer so that the data can be transferred reliably and in order, regardless of any fragmentation, disordering, or packet loss that occurs during transmission. For every byte transmitted the sequence number must be incremented. In the first two steps of a 3-way handshaking, both computers exchange an initial sequence number (ISN). This number can be arbitrary, and should in fact be unpredictable, in order to avoid a TCP sequence prediction attack.
TCP primarily uses a cumulative acknowledgment scheme, where the receiver sends an acknowledgment (ACK) signifying that the receiver has received all data preceding the acknowledged sequence number. Essentially, the first data byte in a segment is assigned a sequence number, which is inserted in the sequence number field, and the receiver sends an ACK specifying the sequence number of the next byte they expect to receive. For example, if computer A sends 4 bytes with a sequence number of 100 (conceptually, the four bytes would have a sequence number of 100, 101, 102, & 103 assigned), then the receiver would send back an ACK of 104 since that is the next byte it expects to receive in the next packet. By sending an ACK of 104, the receiver is signaling that it received bytes 100, 101, 102, & 103 correctly. If, by some chance, the last two bytes were corrupted then an ACK value of 102 would be sent since 100 & 101 were received successfully. If the sender infers that data has been lost in the network, it retransmits the data.
TCP uses a number of mechanisms to achieve high performance aimed at congestion control and avoidance of congestion collapse, where network performance can fall by several orders of magnitude. These mechanisms control the rate of data entering the network, keeping the data flow below a rate that would trigger collapse. Acknowledgments (ACKs) for data sent, or lack of ACKs, are used by senders to infer network conditions between the TCP sender and receiver. Coupled with timers, TCP senders and receivers can alter the behavior of the flow of data. This is more generally referred to as congestion control and/or network congestion avoidance.
Modern implementations of TCP contain four intertwined algorithms: slow-start, congestion avoidance, fast retransmit, and fast recovery. In addition, senders employ a retransmission timer that is based on the estimated round-trip time (RTT) between the sender and receiver, as well as the variance in this round trip time. There are subtleties in the estimation of RTT. For example, senders must be careful when calculating RTT samples for retransmitted packets; typically they use Karn's Algorithm or TCP timestamps. These individual RTT samples are then averaged over time to create a Smoothed Round Trip Time (SRTT) using Jacobson's algorithm. This SRTT value is what is finally used as the round-trip time estimate.
Turning to fast retransmit (FR), this is an enhancement to TCP which reduces the time a sender waits before retransmitting a lost segment. A TCP sender uses timers to recognize lost segments. If an acknowledgement is not received for a particular segment within a specified time (a function of the estimated round-trip delay time), the sender will assume the segment was lost in the network, and will retransmit the segment. The fast retransmit enhancement works as follows: if a TCP sender receives three duplicate acknowledgements (dupacks) with the same acknowledge number (that is, a total of four acknowledgements with the same acknowledgement number), the sender can be reasonably confident that the segment with the next higher sequence number was dropped, and will not arrive out of order. The sender will then retransmit the packet that was presumed dropped before waiting for its timeout. As previously suggested, the fast retransmit threshold (FRT) is a hard-coded 3, i.e., 3 dupacks or dupack-thresh, and involves use of a backtracking algorithm.